import org.junit.Test;

import static com.study.util.LogUtil.info;
import static java.lang.Integer.max;

/**
 * Calculate depth of a full Binary tree from Preorder
 * <p>
 * Given preorder of a binary tree, calculate its depth(or height)
 * [starting from depth 0]. The preorder is given as a string with two possible characters.
 * <p>
 * ‘l’ denotes the leaf
 * ‘n’ denotes internal node
 * The given tree can be seen as a full binary tree where every node has 0
 * or two children. The two children of a node can ‘n’ or ‘l’ or mix of both.
 * <p>
 * Examples :
 * <p>
 * Input  : nlnll
 * Output : 2
 * Explanation :
 * n
 * / \
 * l  n
 * / \
 * l   l
 * <p>
 * Input  : nlnnlll
 * Output : 3
 * n
 * / \
 * l   n
 * / \
 * n   l
 * / \
 * l   l
 * <p>
 * Recommended: Please try your approach on {IDE} first, before moving on to the solution.
 * <p>
 * Preorder of the binary tree is given so traverse
 * Also, we would be given a string of char (formed of ‘n’ and ‘l’), so there is no need to implement tree also.
 * <p>
 * The recursion function would be:
 * 1) Base Case: return 0; when tree[i] = ‘l’ or i >= strlen(tree)
 * 2) find_depth( tree[i++] ) //left subtree
 * 3) find_depth( tree[i++] ) //right subtree
 * <p>
 * Where i is the index of the string tree.
 * <p>
 * 2019-05-27 23:24
 **/
@SuppressWarnings("all")
public class CalculateDepthOfAFullBinaryTreeFromPreorder {

    int findDepth(String tree, int n) {
        return dfs(tree, n, 0);
    }

    int dfs(String str, int max, int index) {
        if (index >= max || str.charAt(index) == 'l')
            return 0;

        int left = dfs(str, max, index++);

        int right = dfs(str, max, index++);

        return max(left, right) + 1;
    }

    @Test
    public void test() {
        info(findDepth("nlnnlll", 7));
    }
}












































/*
int findDepth(String tree, int n) {
    return dfs(tree, n, 0);
}

int dfs(String tree, int n, int index) {
    if (index >= n || tree.charAt(index) == 'l')
        return 0;

    int left = dfs(tree, n, index++);

    int right = dfs(tree, n, index++);

    return max(left, right) + 1;
}
*/